class Solution {
    ListNode *head;
public:
    Solution(ListNode* head) {
        this->head = head;
    }
    
    int getRandom() {
        int i = 1, ans = 0;

        for(auto node = head; node; node = node->next)
        {
            if(rand() % i == 0) // 1/i 的概率选中
            {
                ans = node->val;
            }
            ++i;
        }
        return ans;
    }
};